#include <iostream>
#include <vector>

template <class RanIt>
size_t longest_increasing_subsequence(RanIt first, RanIt last)
{
    // Let n be the number of elements in the sequence.
    size_t n = last - first;

    // Let L be the length of the longest subsequence found so far.
    size_t L = 0;

    // Let A[j-1] be the index of the smallest tail of an increasing 
    // sub-sequence of length j found so far.
    size_t *A = new size_t[n];
    
    // Check each successive element.
    for (size_t j = 0; j < n; j++)
    {
        // Perform a binary search to find the largest tail among the 
        // currently-found increasing subsequences that is smaller than a[j].
        // Returns upper: the index that is one past such an element.
        size_t lower = 0, upper = L;
        while (lower < upper)
        {
            size_t mid = lower + (upper - lower) / 2; // avoid int overflow
            if (first[A[mid]] < first[j])
                lower = mid + 1;
            else 
                upper = mid;
        }

        // Grow L if this element is larger than all previous elements.
        if (upper == L)
            ++L;

        // Update the found element.
        A[upper] = j;
    }
    delete [] A;
    return L;
}

int main()
{
    size_t N;
    while (std::cin >> N)
    {
        std::vector<int> a(N);
        for (size_t i = 0; i < N; i++)
            std::cin >> a[i];

        size_t L = longest_increasing_subsequence(a.begin(), a.end());
        std::cout << L << std::endl;
    }
    return 0;
}
